package com.cn.algorithm.two.greedy;

public class Greedy {
    public static void main(String[] args) {
        System.out.println(coins1(41));
    }

    /*
     * 贪心算法：通过局部最优解，企图推导出全局最优解
     */
    public static int coins1(int coins) {
        int[] arr = {1, 5, 20, 25};
        int index = arr.length - 1;
        int count = 0;
        while (index >= 0 && coins > 0) {
            while (coins >= arr[index]) {
                coins -= arr[index];
                count++;
            }
            index--;
        }
        return count;
    }
}
